//
// Created by Administrator on 2021/5/24.
//

#ifndef CPPLEETCODING_MAXHBLT_H
#define CPPLEETCODING_MAXHBLT_H

#include <iostream>
#include <queue>

using namespace std;

template<class T>
struct binaryTreeNode { // 二叉树节点定义
    T element;
    binaryTreeNode<T> *leftChild, *rightChild;

    binaryTreeNode() { leftChild = rightChild = nullptr; };

    binaryTreeNode(const T &theElement) {
        element = theElement;
        leftChild = rightChild = nullptr;
    }

    binaryTreeNode(const T &theElement, binaryTreeNode *theLeftChild, binaryTreeNode *theRightChild) {
        element = theElement;
        leftChild = theLeftChild;
        rightChild = theRightChild;
    }

};

template<class T>
class maxHblt {
public:
    void melt(maxHblt<T> &theHblt);

    void push(const T &theElement);

    void pop();

    void initializer(T *theElement, int theSize);

    void initializer(vector<T> &v, int theSize);

    T top();

private:
    binaryTreeNode<pair<int, T>> *root; // 指向根的指针
    int treeSize;  // 树的节点个数
    void meld(binaryTreeNode<pair<int, T>> *&x, binaryTreeNode<pair<int, T>> *&y);

};

template<class T>
void maxHblt<T>::meld(binaryTreeNode<pair<int, T>> *&x, binaryTreeNode<pair<int, T>> *&y) {
    /**
     * pair第一个元素是节点的s值，第二个元素是优先级队列元素
     * 合并分别以*x *y为根的两棵左高树
     * 合并后的左高树以x为根，返回x的指针
     */
    if (y == nullptr) return;// y为空
    if (x == nullptr) { // x为空
        x = y;
        return;
    }
    // x y 都不为空 必要时交换x y
    if (x->element.second < y->element.second) {
        swap(x, y);
    }
    meld(x->rightChild, y);
    // 如果需要，交换x的子树，然后设置x->element.first的值
    if (x->leftChild == nullptr) {
        // 左子树为空，交换子树
        x->leftChild = x->rightChild;
        x->rightChild = nullptr;
        x->element.first = 1;
    } else {
        // 只有左子树的s值较小时才交换
        if (x->leftChild->element.first < x->rightChild->element.first) {
            swap(x->leftChild, x->rightChild);
        }
        // 更新x的s值
        x->element.first = x->rightChild->element.first + 1;
    }
}

template<class T>
void maxHblt<T>::melt(maxHblt<T> &theHblt) {
    // 把左高树*this和theHblt合并
    meld(root, theHblt.root);
    treeSize += theHblt.treeSize;
    theHblt.root = nullptr;
    theHblt.treeSize = 0;
}

template<class T>
void maxHblt<T>::push(const T &theElement) {
    // 把元素Element插入左高树
    // 建立只有一个节点的左高树
    auto *q = new binaryTreeNode<pair<int, T>>(pair<int, T>(1, theElement));
    // 将左高树q和原树合并
    meld(root, q);
    ++treeSize;
}

template<class T>
void maxHblt<T>::pop() {
    // 删除最大元素
    if (root == nullptr) {
        cout << "not element left" << endl;
        return;
    }
    // 树不空
    binaryTreeNode<pair<int, T>> *left = root->leftChild, *right = root->rightChild;
    delete root;
    root = left;
    meld(root, right);
    --treeSize;
}

template<class T>
void maxHblt<T>::initializer(T *theElement, int theSize) {
    // 用数组theElement[1:theSize]建立左高树
    queue<binaryTreeNode<pair<int, T>> *> q;
    this->root = nullptr;
    // 初始化树的队列
    for (int i = 0; i < theSize; ++i) {
        //建立只有一个节点的树
        q.push(new binaryTreeNode<pair<int, T>>(make_pair(1, theElement[i])));
    }
    // 从队列中重复取出两棵树合并
    for (int i = 1; i < theSize; ++i) {
        // 从队列中删除两棵树合并
        auto b = q.front();
        q.pop();
        auto c = q.front();
        q.pop();
        meld(b, c);
        q.push(b);
    }
    if (theSize > 0) root = q.front();
    treeSize = theSize;
}

template<class T>
T maxHblt<T>::top() {
    return root->element.second;
}

template<class T>
void maxHblt<T>::initializer(vector<T> &v, int theSize) {
// 用数组theElement[1:theSize]建立左高树
    queue<binaryTreeNode<pair<int, T>> *> q;
    this->root = nullptr;
    // 初始化树的队列
    for (int i = 0; i < theSize; ++i) {
        //建立只有一个节点的树
        q.push(new binaryTreeNode<pair<int, T>>(make_pair(1, v[i])));
    }
    // 从队列中重复取出两棵树合并
    for (int i = 1; i < theSize; ++i) {
        // 从队列中删除两棵树合并
        auto b = q.front();
        q.pop();
        auto c = q.front();
        q.pop();
        meld(b, c);
        q.push(b);
    }
    if (theSize > 0) root = q.front();
    treeSize = theSize;
}


#endif //CPPLEETCODING_MAXHBLT_H
